{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #每日温度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: dailyTemperatures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每日温度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请根据每日 <code>气温</code> 列表 <code>temperatures</code>&nbsp;，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用&nbsp;<code>0</code> 来代替。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> <code>temperatures</code> = [73,74,75,71,69,72,76,73]\n",
    "<strong>输出:</strong>&nbsp;[1,1,4,2,1,1,0,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> temperatures = [30,40,50,60]\n",
    "<strong>输出:</strong>&nbsp;[1,1,1,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> temperatures = [30,60,90]\n",
    "<strong>输出: </strong>[1,1,0]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;temperatures.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>30 &lt;=&nbsp;temperatures[i]&nbsp;&lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 739&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/daily-temperatures/\">https://leetcode-cn.com/problems/daily-temperatures/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [iIQa4I](https://leetcode.cn/problems/iIQa4I/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [iIQa4I](https://leetcode.cn/problems/iIQa4I/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        dp = [0]*n\n",
    "        for i in range(n-2, -1, -1):\n",
    "            next_id = i+1\n",
    "            while True:\n",
    "                if temperatures[next_id] > temperatures[i]:\n",
    "                    dp[i] = next_id-i\n",
    "                    break\n",
    "                elif dp[next_id] == 0:\n",
    "                    dp[i] = 0\n",
    "                    break\n",
    "                else:\n",
    "                    next_id = next_id + dp[next_id]\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        length = len(temperatures)\n",
    "        ans = [0] * length\n",
    "\n",
    "        for i in range(1,length):\n",
    "            if temperatures[i] > temperatures[i-1]:\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    if ans[j] == 0 and temperatures[j] < temperatures[i]:\n",
    "                        ans[j] = i - j\n",
    "                    elif temperatures[j] >= temperatures[i]:\n",
    "                        break\n",
    "        # ans = [0 if x is None else x for x in ans]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        if n <= 1:\n",
    "            return [0]\n",
    "        \n",
    "        res = [0] * n\n",
    "        temp = [[temperatures[n-1],n-1]]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            while len(temp) > 0 and temperatures[i] >= temp[-1][0]:\n",
    "                del temp[-1]\n",
    "            if len(temp) > 0:\n",
    "                res[i] = temp[-1][1] - i\n",
    "            temp.append([temperatures[i],i])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temps: List[int]) -> List[int]:\n",
    "        n = len(temps)\n",
    "        ans, nxt, big = [0]*n, dict(), 10**9\n",
    "        for i in range(n-1,-1,-1):\n",
    "            warmer_index = min(nxt.get(t,big) for t in range(temps[i]+1, 102))#拟定初值语句\n",
    "            if warmer_index != big:\n",
    "                ans[i] = warmer_index - i\n",
    "            nxt[temps[i]] = i \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = temperatures.__len__()\n",
    "        arr = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            j = i+1\n",
    "            while j < n:\n",
    "                if temperatures[j] > temperatures[i]:\n",
    "                    arr[i] = j-i\n",
    "                    break\n",
    "                elif arr[j] == 0:\n",
    "                    break\n",
    "                else:\n",
    "                    j += arr[j]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        def findMinIdx(arr,target):\n",
    "            l=0\n",
    "            r=len(arr)\n",
    "            while l<r:\n",
    "                mid = l+(r-l)//2\n",
    "                if arr[mid]<=target:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid\n",
    "            return l\n",
    "\n",
    "        length = len(temperatures)\n",
    "        wait_list = [0]*length\n",
    "        rise_stack = []\n",
    "        rise_idx_stack = []\n",
    "        for i in range(length-1,-1,-1):\n",
    "            t = temperatures[i]\n",
    "            idx = findMinIdx(rise_stack,t)\n",
    "            if idx<len(rise_stack):\n",
    "                wait_list[i] = rise_idx_stack[idx]-i\n",
    "            while rise_stack and rise_stack[0]<=t:\n",
    "                rise_stack.pop(0)\n",
    "                rise_idx_stack.pop(0)\n",
    "            rise_stack = [t]+rise_stack\n",
    "            rise_idx_stack = [i]+rise_idx_stack\n",
    "        return wait_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        days = [0]*n\n",
    "        \n",
    "        maxtem = temperatures[-1]\n",
    "        nowtem = 0\n",
    "        for i in range(n-2,-1,-1):\n",
    "            nowtem = temperatures[i]\n",
    "            \n",
    "            if maxtem <= nowtem:\n",
    "                days[i] = 0\n",
    "                maxtem = nowtem\n",
    "            else:\n",
    "                j = i+1\n",
    "                while j<n:\n",
    "                    if nowtem<temperatures[j]:\n",
    "                        days[i] = j-i\n",
    "                        break\n",
    "                    elif nowtem == temperatures[j]:\n",
    "                        if days[j] == 0:\n",
    "                            days[i] = 0\n",
    "                        else:\n",
    "                            days[i] = days[j]+j-i\n",
    "                        break\n",
    "                    else:\n",
    "                        if days[j]==0:\n",
    "                            days[i] = 0\n",
    "                            maxtem = nowtem\n",
    "                            break\n",
    "                        else:\n",
    "                            j = j+days[j]\n",
    "            \n",
    "        return days\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        ans = [0] * len(temperatures)\n",
    "        for index, temperature in enumerate(temperatures):\n",
    "            while stack and temperature > temperatures[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                ans[idx] = index - idx\n",
    "            stack.append(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        days = [0]*n\n",
    "        \n",
    "        maxtem = temperatures[-1]\n",
    "        nowtem = 0\n",
    "        for i in range(n-2,-1,-1):\n",
    "            nowtem = temperatures[i]\n",
    "            \n",
    "            if maxtem <= nowtem:\n",
    "                days[i] = 0\n",
    "                maxtem = nowtem\n",
    "            else:\n",
    "                j = i+1\n",
    "                while j<n:\n",
    "                    if nowtem<temperatures[j]:\n",
    "                        days[i] = j-i\n",
    "                        break\n",
    "                    elif nowtem == temperatures[j]:\n",
    "                        if days[j] == 0:\n",
    "                            days[i] = 0\n",
    "                        else:\n",
    "                            days[i] = days[j]+j-i\n",
    "                        break\n",
    "                    else:\n",
    "                        if days[j]==0:\n",
    "                            days[i] = 0\n",
    "                            maxtem = nowtem\n",
    "                            break\n",
    "                        else:\n",
    "                            j = j+days[j]\n",
    "            \n",
    "        return days\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        \n",
    "        stack =[]\n",
    "        n = len(temperatures)\n",
    "        ans = [0]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and temperatures[i]>temperatures[stack[-1]]:\n",
    "                l = stack.pop()\n",
    "                ans[l] = i-l\n",
    "            stack.append(i)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(temperatures)\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            while stack and temperatures[i]>temperatures[stack[-1]]:\n",
    "                index = stack.pop()\n",
    "                ans[index] = i-index\n",
    "            stack.append(i)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        res = [0] * len(temperatures)\n",
    "        stack = [0]\n",
    "        for i in range(1, len(temperatures)):\n",
    "            if temperatures[i] <= temperatures[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and temperatures[i] > temperatures[stack[-1]]:\n",
    "                    idx = stack.pop()\n",
    "                    res[idx] = i - idx \n",
    "                \n",
    "                stack.append(i)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, A: List[int]) -> List[int]:\n",
    "        N = len(A)\n",
    "        Q = deque([])\n",
    "        ret = [ 0 ] * N\n",
    "        for i in range(N-1, -1, -1):\n",
    "            while Q and A[Q[0]] <= A[i]:\n",
    "                Q.popleft()\n",
    "            if Q:\n",
    "                ret[i] = Q[0] - i\n",
    "            Q.appendleft(i)\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        st = []\n",
    "        res = [0] * len(temperatures)\n",
    "        for idx, t in enumerate(temperatures):\n",
    "            while st and temperatures[st[-1]] < t:\n",
    "                i = st.pop()\n",
    "                res[i] = idx - i\n",
    "            st.append(idx)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures):\n",
    "        stack, ret = [], [0] * len(temperatures)\n",
    "        for i, num in enumerate(temperatures):\n",
    "            while stack and temperatures[stack[-1]] < num:\n",
    "                index = stack.pop()\n",
    "                ret[index] = i - index\n",
    "            stack.append(i)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans=[0]*len(temperatures)\n",
    "        s=[] #单调栈\n",
    "        for i,num in enumerate(temperatures):\n",
    "            while s and num>temperatures[s[-1]]:\n",
    "                index=s.pop()\n",
    "                ans[index]=i-index\n",
    "            s.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        # for i, t in enumerate(temperatures):\n",
    "        #     while(st and t > temperatures[st[-1]]):\n",
    "        #         j = st.pop()\n",
    "        #         ans[j] = i - j\n",
    "        #     st.append(i)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            t = temperatures[i]\n",
    "            while(st and temperatures[st[-1]] <= t):\n",
    "                st.pop()\n",
    "            if(not st):\n",
    "                ans[i] = 0\n",
    "            else:\n",
    "                ans[i] = st[-1] - i\n",
    "            st.append(i)\n",
    "        return ans\n",
    "\n",
    "#输出一个列表ans，ans[i]代表第i天要想观测到更高的气温，至少需要等待的天数，如果没有则用0代替\n",
    "#ans[i]可以抽象成lst[i]与右边第一个大于lst[i]的下标j的差值dif, j > i, lst[j] > lst[i], min(j1, j2....)\n",
    "#或者是找出第i数第一个右边更大的数，这个数的下标与第i个数的下标之差，即距离之差\n",
    "#单调栈思路：从左到右序列元素记录下标,维护成降序序列\n",
    "#一旦有插入元素大于栈顶，循环弹出栈顶，直到栈顶元素小于等于带插入元素，将带插入元素入栈\n",
    "\n",
    "\n",
    "#单调栈思路，从右到左，也维护成降序序列\n",
    "#如果栈顶小于等于插入元素，弹出，直到栈为空或者栈顶大于待插入元素，计算下标差\n",
    "#如果栈顶大于待插入元素, 计算下标差，入栈"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures):\n",
    "        stack, ret = [], [0] * len(temperatures)\n",
    "        for i, num in enumerate(temperatures):\n",
    "            while stack and temperatures[stack[-1]] < num:\n",
    "                index = stack.pop()\n",
    "                ret[index] = i - index\n",
    "            stack.append(i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while len(stack) > 0 and temperatures[i] >= stack[-1][0]:\n",
    "                stack.pop()\n",
    "            ans[i] = stack[-1][1] - i if len(stack) > 0 else 0\n",
    "            stack.append([temperatures[i], i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, t: List[int]) -> List[int]:\n",
    "        ans=[0]*len(t)\n",
    "        st = []\n",
    "        for i in range(len(t)):\n",
    "            while st and t[i]>t[st[-1]]:\n",
    "                idx = st.pop()\n",
    "                ans[idx]=i-idx \n",
    "            st.append(i)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        temp_len = len(temperatures)\n",
    "        if temp_len == 0:\n",
    "            return []\n",
    "              \n",
    "        result_list = [0] * temp_len\n",
    "        temp_hash = [[x, 0] for x in range(0,101)]\n",
    "\n",
    "        for idx in range(temp_len-1,-1,-1):   \n",
    "            min_diff = float('inf')         \n",
    "            temp_hash[temperatures[idx]][1] = idx           \n",
    "            for x in range(temperatures[idx]+1, 101):\n",
    "                if (temp_hash[x][1] > idx) and ((temp_hash[x][1] - idx) < min_diff):\n",
    "                    min_diff = temp_hash[x][1] - idx\n",
    "            \n",
    "            if min_diff != float('inf'):\n",
    "                result_list[idx] = min_diff\n",
    "\n",
    "\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, nums: List[int]) -> List[int]:\n",
    "        st,ans = [],[0]*(len(nums))\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if not st or nums[st[-1]]>nums[i]:\n",
    "                st.append(i)\n",
    "            else:\n",
    "                while st and nums[st[-1]]<=nums[i]:st.pop()\n",
    "                st.append(i)\n",
    "            ans[i]=0 if len(st)==1 else st[-2]-i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, A: List[int]) -> List[int]:\n",
    "        N = len(A)\n",
    "        Q = deque([])\n",
    "        ret = [ 0 ] * N\n",
    "        for i in range(N-1, -1, -1):\n",
    "            while Q and A[Q[0]] <= A[i]:\n",
    "                Q.popleft()\n",
    "            if Q:\n",
    "                ret[i] = Q[0] - i\n",
    "            Q.appendleft(i)\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans, nxt, big = [0] * n, dict(), 10**9\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            warmer_index = min(nxt.get(t, big) for t in range(temperatures[i] + 1, 102))\n",
    "            if warmer_index != big:\n",
    "                ans[i] = warmer_index - i\n",
    "            nxt[temperatures[i]] = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "\n",
    "        st = []\n",
    "        res = [0] * len(temperatures)\n",
    "        for i in range(len(temperatures)):\n",
    "            while st and temperatures[i] > temperatures[st[-1]]:\n",
    "                j = st.pop()\n",
    "                res[j] = i - j\n",
    "            st.append(i)\n",
    "\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        stack = []\n",
    "        res = [0] * n\n",
    "        for i,value in enumerate(temperatures):\n",
    "            while len(stack) > 0 and value > temperatures[stack[-1]]:\n",
    "                res[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack, res = [], [0] * len(temperatures)\n",
    "        for i, num in enumerate(temperatures):\n",
    "            while stack and temperatures[stack[-1]] < num:\n",
    "                index = stack.pop()\n",
    "                res[index] = i - index\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n;\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            t = temperatures[i]\n",
    "            while st and t >=  temperatures[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                ans[i] = st[-1] - i\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        st = []\n",
    "        ans = [0] * n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            # print(i,st)\n",
    "            while st and temperatures[i] >= temperatures[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                ans[i] = st[-1] - i \n",
    "            st.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# labuladong 下一个更大元素，用栈\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-daeca/dan-diao-z-1bebe/\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        stack = [] # 定义栈，里面存储的是idx，下一个更大元素对应的idx是多少\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and temperatures[stack[-1]] <= temperatures[i]:\n",
    "                stack.pop()\n",
    "            ans[i] = stack[-1] - i if stack else 0\n",
    "            stack.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans = [0 for _ in range(len(temperatures))]\n",
    "        stack = []\n",
    "        for i in range(len(temperatures)):\n",
    "            if not stack or temperatures[stack[-1]] >= temperatures[i]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while temperatures[stack[-1]] < temperatures[i]:\n",
    "                    temp = stack.pop()\n",
    "                    ans[temp] = i - temp\n",
    "                    if not stack: break\n",
    "                stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        s = []\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while s and temperatures[s[-1]] <= temperatures[i] :\n",
    "                s.pop()\n",
    "            ans[i] =  s[-1] - i if s else 0\n",
    "            s.append(i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(temperatures)\n",
    "        res = [0] * n\n",
    "        for i in range(n):\n",
    "            while stack and temperatures[stack[-1]] < temperatures[i]:\n",
    "                pre = stack.pop()\n",
    "                res[pre] = i - pre\n",
    "            stack.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0]*n\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and temperatures[st[-1]] <= temperatures[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                ans[i] = st[-1]-i\n",
    "            st.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        # 存放答案的数组\n",
    "        res = [0 for _ in range(n)]\n",
    "        s = [] \n",
    "        # 倒着往栈里放\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # 判定个子高矮\n",
    "            while s and temperatures[s[-1]] <= temperatures[i]:\n",
    "                # 矮个起开，反正也被挡着了。。。\n",
    "                s.pop()\n",
    "            # nums[i] 身后的更大元素\n",
    "            res[i] = s[-1]-i if s else 0\n",
    "            s.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            t = temperatures[i]\n",
    "            while st and t >= temperatures[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                ans[i] = st[-1] - i\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        s, res = [], [0]*len(temperatures)\n",
    "        for i, num in enumerate(temperatures):\n",
    "            while s and temperatures[s[-1]] < num:\n",
    "                index = s.pop()\n",
    "                res[index] = i - index\n",
    "            s.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n=len(temperatures)\n",
    "        stack,ans=[],[0]*n\n",
    "        for i in range(n):\n",
    "            while stack and temperatures[i]>temperatures[stack[-1]]:\n",
    "                p=stack.pop()\n",
    "                ans[p]=i-p\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        res = [0] * len(temperatures)\n",
    "        stack = [0]\n",
    "        for i in range(1, len(temperatures)):\n",
    "            if temperatures[i] <= temperatures[stack[-1]]:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and temperatures[i] > temperatures[stack[-1]]:\n",
    "                    idx = stack.pop()\n",
    "                    res[idx] = i - idx \n",
    "                \n",
    "                stack.append(i)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        ans = [0]*len(temperatures)\n",
    "        for i in range(len(temperatures)):\n",
    "            if len(res) == 0:\n",
    "                res.append(i)\n",
    "            else:\n",
    "                while len(res)>0 and temperatures[i] > temperatures[res[-1]]:\n",
    "                    cur = res.pop(-1)\n",
    "                    ans[cur] = i - cur\n",
    "                res.append(i)\n",
    "        return ans\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        l = [0]*n\n",
    "        ans = [-1]*n\n",
    "        for i in range(n):\n",
    "            if not l:\n",
    "                l.append(i)\n",
    "            else:\n",
    "                while l and temperatures[i] >= temperatures[l[-1]]:\n",
    "                    x = l.pop()    \n",
    "                    ans[x] = i\n",
    "                l.append(i)\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if ans[i] != -1 and temperatures[ans[i]] == temperatures[i]:\n",
    "                ans[i] = ans[ans[i]]\n",
    "        for i in range(n):\n",
    "            if ans[i] !=-1:\n",
    "                ans[i] = ans[i] - i\n",
    "            else:\n",
    "                ans[i] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0]*n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and temperatures[stack[-1]] < temperatures[i]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = i-ind\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        #单调栈\n",
    "        n=len(temperatures)\n",
    "        ans=[0]*n\n",
    "        st=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and temperatures[i]>=temperatures[st[-1]]:\n",
    "                st.pop()\n",
    "            \n",
    "            if len(st)!=0:\n",
    "                ans[i]=st[-1]-i\n",
    "            \n",
    "            st.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans = [0] * (len(temperatures))\n",
    "        st = []\n",
    "        for i,x in enumerate(temperatures):\n",
    "            while st and x>temperatures[st[-1]]:\n",
    "                print(x,temperatures[st[-1]])\n",
    "                ans[st[-1]] = (i-st[-1])\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        st = []\n",
    "        for i,index in enumerate(temperatures):\n",
    "            while st and index > temperatures[st[-1]]:\n",
    "                j = st.pop()\n",
    "                ans[j] = i - j\n",
    "            st.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        res =[0 for _ in range(n)]\n",
    "        stack = []\n",
    "        for i,t in enumerate(temperatures):\n",
    "            while stack and t > temperatures[stack[-1]]:\n",
    "                j = stack.pop()\n",
    "                res[j] = i - j\n",
    "            stack.append(i)\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0]*n\n",
    "        st = []\n",
    "        for i,t in enumerate(temperatures):\n",
    "            while st and t > temperatures[st[-1]]:\n",
    "                j = st.pop()\n",
    "                ans[j] = i - j\n",
    "            st.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        mono_stack = list()\n",
    "        for i in range(n):\n",
    "            while mono_stack and temperatures[mono_stack[-1]] < temperatures[i]:\n",
    "                b = mono_stack.pop()\n",
    "                ans[b] = i - b\n",
    "            mono_stack.append(i)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            temperature = temperatures[i]\n",
    "            while stack and temperature > temperatures[stack[-1]]:\n",
    "                prev_index = stack.pop()\n",
    "                ans[prev_index] = i - prev_index\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack=[]\n",
    "        ans=[0]*len(temperatures)\n",
    "        for i in range(len(temperatures)):\n",
    "            while stack and temperatures[stack[-1]]<temperatures[i]:\n",
    "                ans[stack[-1]]=i-stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(temperatures)\n",
    "        ans = [0]*n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            cur = temperatures[i]\n",
    "            while stack and cur >temperatures[stack[-1]]:\n",
    "                pre = stack.pop()\n",
    "                ans[pre] = i-pre\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        length = len(temperatures)\n",
    "        ans = [0] * length\n",
    "        stack = []\n",
    "        for i in range(length):\n",
    "            temperature = temperatures[i]\n",
    "            while stack and temperature > temperatures[stack[-1]]:\n",
    "                prev_index = stack.pop()\n",
    "                ans[prev_index] = i - prev_index\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans = [0 for _ in range(len(temperatures))]\n",
    "        stack = []\n",
    "        for i, t in enumerate(temperatures):\n",
    "            while stack and temperatures[stack[-1]] < t:\n",
    "                left = stack.pop()\n",
    "                ans[left] = i - left\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        l = [0]*n\n",
    "        ans = [-1]*n\n",
    "        for i in range(n):\n",
    "            if not l:\n",
    "                l.append(i)\n",
    "            else:\n",
    "                while l and temperatures[i] >= temperatures[l[-1]]:\n",
    "                    x = l.pop()\n",
    "                    \n",
    "                    ans[x] = i\n",
    "                l.append(i)\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if ans[i] != -1 and temperatures[ans[i]] == temperatures[i]:\n",
    "                ans[i] = ans[ans[i]]\n",
    "        for i in range(n):\n",
    "            if ans[i] !=-1:\n",
    "                ans[i] = ans[i] - i\n",
    "            else:\n",
    "                ans[i] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        ans = [0 for i in temperatures]\n",
    "        for i,tem in enumerate(temperatures):\n",
    "            while len(stack) and tem > temperatures[stack[-1]]:\n",
    "                ind = stack.pop()\n",
    "                ans[ind] = i-ind\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        l = []\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            if not l:\n",
    "                l.append(i)\n",
    "            else:\n",
    "                while l and temperatures[i] > temperatures[l[-1]]:\n",
    "                    x = l.pop()    \n",
    "                    ans[x] = i-x\n",
    "                l.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        s = []\n",
    "        n = len(temperatures)\n",
    "\n",
    "        ans = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            while s and temperatures[s[-1]] < temperatures[i]:\n",
    "                ans[s[-1]] = i - s[-1]\n",
    "                s.pop()\n",
    "            s.append(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, tem: List[int]) -> List[int]:\n",
    "        n = len(tem)\n",
    "        arr = []\n",
    "        ans = []\n",
    "        for i in range(-1, -n-1 ,-1):\n",
    "            t = tem[i]\n",
    "            res = 1\n",
    "            while arr and t >= arr[-1][0]:\n",
    "                p = arr.pop()\n",
    "                res += p[1]\n",
    "            if len(arr) == 0:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                ans.append(res)    \n",
    "            arr.append((t, res))\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans=[0]*len(temperatures)\n",
    "        L=[]\n",
    "        for i in range(len(temperatures)):\n",
    "            while(len(L)>0 and L[-1][0]<temperatures[i]):\n",
    "                a,b=L.pop()\n",
    "                ans[b]=i-b\n",
    "            L.append([temperatures[i],i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        n = len(temperatures)\n",
    "        arr = [0] * n\n",
    "        for i in range(n):\n",
    "            if stack and stack[-1][0] < temperatures[i]:\n",
    "                while stack and stack[-1][0] < temperatures[i]:\n",
    "                    temp, idx = stack.pop()\n",
    "                    arr[idx] = i - idx\n",
    "            stack.append((temperatures[i], i))\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "\t\tresult = [0] * len(temperatures)\n",
    "\t\tstck = []\n",
    "\t\tfor i, temp in enumerate(temperatures):\n",
    "\t\t\twhile stck and stck[-1][0] < temp:\n",
    "\t\t\t\t_, prev = stck.pop()\n",
    "\t\t\t\tresult[prev] = i - prev\n",
    "\t\t\tstck.append((temp, i))\n",
    "\t\treturn result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ListA = []\n",
    "        output = []\n",
    "        valueIndex = {}\n",
    "\n",
    "        for index, value in enumerate(temperatures):\n",
    "            output.append(0)\n",
    "\n",
    "            while ListA:\n",
    "                if ListA[0]< value:\n",
    "                    a = heapq.heappop(ListA)\n",
    "                    cur_index = valueIndex[a].pop(0)\n",
    "                    output[cur_index] = index - cur_index\n",
    "                else:\n",
    "                    break\n",
    "            if value in valueIndex:\n",
    "                valueIndex[value].append(index)\n",
    "            else:\n",
    "                valueIndex[value] = [index]\n",
    "            heapq.heappush(ListA, value)\n",
    "\n",
    "        \n",
    "        return output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        len_ = len(temperatures)\n",
    "        wait = [0 for _ in range(len_)]\n",
    "        stack = []\n",
    "        for idx in range(len_):\n",
    "            #if not stack or temperatures[idx]<temperatures[stack[-1]]:\n",
    "            #    stack.append(idx)\n",
    "            #    continue\n",
    "\n",
    "            while len(stack)>0 and temperatures[idx]>temperatures[stack[-1]]:\n",
    "                temp = stack.pop()\n",
    "                wait[temp] = idx-temp\n",
    "            stack.append(idx)\n",
    "        return (wait)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        length=len(temperatures)\n",
    "        ans=[0 for _ in range(length)]\n",
    "        queue=[]\n",
    "        for i in range(len(temperatures)):\n",
    "                while queue and temperatures[queue[-1]]<temperatures[i]:\n",
    "                    index=queue.pop(-1)\n",
    "                    ans[index]=i-index\n",
    "                queue.append((i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0 for _ in range(n)]\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            temp = temperatures[i]\n",
    "            while stack and temp > temperatures[stack[-1]]:\n",
    "                pre_idx = stack.pop()\n",
    "                ans[pre_idx] = i-pre_idx\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        \n",
    "        self.stack = [0]*len(temperatures)\n",
    "        self.r = 0\n",
    "        self.ans = [0]*len(temperatures)\n",
    "        \n",
    "        for i in range(len(temperatures)):\n",
    "            while self.r>0 and temperatures[i]>temperatures[self.stack[self.r-1]]:\n",
    "                self.r -= 1\n",
    "                cur = self.stack[self.r]\n",
    "                self.ans[cur] = i-cur\n",
    "            self.stack[self.r] = i\n",
    "            self.r += 1\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        ans = [0] * len(temperatures)\n",
    "        for i in range(len(temperatures)-1):\n",
    "            if temperatures[i] < temperatures[i+1]:\n",
    "                ans[i] = 1\n",
    "                while stack and stack[-1][0] < temperatures[i+1]:\n",
    "                    cur = stack.pop()\n",
    "                    ans[cur[1]]=(i+1-cur[1])\n",
    "            else:\n",
    "                stack.append((temperatures[i],i))\n",
    "            #print(i,ans,stack)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = []\n",
    "        ans = [0] * len(temperatures)\n",
    "        for i in range(len(temperatures)-1):\n",
    "            if temperatures[i] < temperatures[i+1]:\n",
    "                ans[i] = 1\n",
    "                while stack and stack[-1][0] < temperatures[i+1]:\n",
    "                    cur = stack.pop()\n",
    "                    ans[cur[1]]=(i+1-cur[1])\n",
    "            else:\n",
    "                stack.append((temperatures[i],i))\n",
    "            #print(i,ans,stack)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        ans = [0 for _ in range(n)]\n",
    "        stack = []\n",
    "        for i in range(n) :\n",
    "            t = temperatures[i]\n",
    "            while stack and t > temperatures[stack[-1]] :\n",
    "                pre = stack.pop()\n",
    "                ans[pre] = i - pre\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, t: List[int]) -> List[int]:\n",
    "        ls=len(t)\n",
    "        q=[]\n",
    "        res=[]\n",
    "        for i in range(ls-1,-1,-1):\n",
    "            while(q and t[i]>=q[-1][0]):\n",
    "                q.pop()\n",
    "            if q:\n",
    "                res.append(q[-1][1]-i)\n",
    "            else:\n",
    "                res.append(0)\n",
    "            q.append([t[i],i])\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        '''\n",
    "        遇到这种比较大小，且站在当前位置，只考虑后面情况的，就想单调栈\n",
    "        '''\n",
    "        stack_list=[]\n",
    "        result=[0]*len(temperatures)\n",
    "        for i in range(len(temperatures)):\n",
    "            if not len(stack_list):\n",
    "                stack_list.append((temperatures[i], i))\n",
    "            else:\n",
    "                if temperatures[i]>stack_list[-1][0]:\n",
    "                    while len(stack_list) and temperatures[i]>stack_list[-1][0]:\n",
    "                        result[stack_list[-1][1]]=i-stack_list[-1][1]\n",
    "                        stack_list.pop(-1)\n",
    "                    stack_list.append((temperatures[i], i))\n",
    "                else:\n",
    "                    stack_list.append((temperatures[i], i))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        # temperatures = [73,74,75,71,69,72,76,73]\n",
    "        n = len(temperatures)\n",
    "        day = [0] * n\n",
    "        visit = []\n",
    "        for i in range(n):\n",
    "\n",
    "            # for j in range(len(visit[:])):\n",
    "            while visit and visit[-1][0] < temperatures[i]:\n",
    "                day[visit[-1][1]] = i - visit[-1][1]\n",
    "                visit.pop()\n",
    "            visit.append([temperatures[i], i])\n",
    "        return day"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        res = [0] * len(temperatures)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(temperatures)):\n",
    "            t = temperatures[i]\n",
    "            if stack:\n",
    "                while stack and t > stack[-1][0]:\n",
    "                    i2 = stack.pop()[1]\n",
    "                    res[i2] = i-i2\n",
    "            stack.append((t,i))\n",
    "        \n",
    "        while stack:\n",
    "            t,i = stack.pop()\n",
    "            res[i] = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        res = [0 for _ in range(len(temperatures))]\n",
    "        # 单调栈\n",
    "        stack = []\n",
    "        for i, num in enumerate(temperatures):\n",
    "            while stack and temperatures[stack[-1]] < num:\n",
    "                res[stack[-1]] = i - stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack=[]\n",
    "        n=len(temperatures)\n",
    "        res=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and temperatures[stack[-1]]<=temperatures[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                res.append(stack[-1])\n",
    "            else:\n",
    "                res.append(0)\n",
    "            stack.append(i)\n",
    "        res=res[::-1]\n",
    "        for i in range(len(res)):\n",
    "            if res[i]!=0:\n",
    "                res[i]-=i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        temp_len = len(temperatures)\n",
    "        if temp_len == 0:\n",
    "            return []\n",
    "       \n",
    "        result_list = [0] * temp_len\n",
    "        stack = [0]\n",
    "        for idx, element in enumerate(temperatures[1:],1):\n",
    "            while(stack):\n",
    "                top_pos = len(stack)-1\n",
    "                if temperatures[stack[top_pos]] < element:\n",
    "                    result_list[stack[top_pos]] = idx - stack[top_pos] \n",
    "                    stack.pop()\n",
    "                    if not stack:\n",
    "                        stack.append(idx)\n",
    "                else:\n",
    "                    stack.append(idx)\n",
    "                    break           \n",
    "\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        temps = [(-1, 1e10)]\n",
    "        res = [0] * len(temperatures)\n",
    "\n",
    "        for i, this_temp in enumerate(temperatures):\n",
    "            while temps:\n",
    "                last_i, last_temp = temps.pop()\n",
    "                if this_temp > last_temp:\n",
    "                    res[last_i] = i - last_i\n",
    "                else:\n",
    "                    temps.append((last_i, last_temp))\n",
    "                    temps.append((i, this_temp))\n",
    "                    break\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        stack = [(100,-1)]\n",
    "        res = [0 for _ in range(len(temperatures))]\n",
    "        for i,temperature in enumerate(temperatures):\n",
    "            while temperature > stack[-1][0]:\n",
    "                index = stack.pop()[1]\n",
    "                res[index] = i - index\n",
    "            stack.append((temperature,i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        ans = [0] * len(temperatures)\n",
    "        wait = [(-1, 101)]   # date, temperature\n",
    "        for i, j in enumerate(temperatures):\n",
    "            while j > wait[-1][1]:\n",
    "                d, t = wait.pop()\n",
    "                ans[d] = i - d\n",
    "            wait.append((i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:\n",
    "        n = len(temperatures)\n",
    "        l = [0]*n\n",
    "        ans = [0]*n\n",
    "        for i in range(n):\n",
    "            if not l:\n",
    "                l.append(i)\n",
    "            else:\n",
    "                while l and temperatures[i] > temperatures[l[-1]]:\n",
    "                    x = l.pop()    \n",
    "                    ans[x] = i-x\n",
    "                l.append(i)\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
